package com.paic.du.lib.sort;
import com.paic.du.lib.*;

public class HeapSort {
	
	public static int right(int i){
		return 2*i + 2;
	}
	
	public static int left(int i){
		return 2*i + 1;
	}
	
	public static void buildMaxHeap(int ori[], int length){
		for(int i=length-1;i>=0;i--){
			int left=left(i);
			int right=right(i);
			if((left<length&&ori[i]>ori[left]))
				Utils.swap(ori, i, left);
			if((right<length&&ori[i]>ori[right]))
				Utils.swap(ori, i, right);
		}
	}
	
	public static void heapSort(int[] ori){
		int length=ori.length;
		while(length>1){
			buildMaxHeap(ori, length);
			Utils.swap(ori, 0, --length);
		}
	}
	
	public static void main(String args[])
	{
		int []ori = Utils.ori;
		int i=0;
		heapSort(ori);
		while(i<ori.length){
			System.out.print(ori[i++]+",");
			
		}
	}
}
